//https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=20
// 2024-10-22

import java.util.Arrays;

public class P029_预测赢家_递归法 {

    public static void main(String[] args) {
        System.out.println(dp(new int[] {5,200,1,3,6}));

    }

    // 最重要：找到dp数组的含义
    private static boolean dp(int[] arr) {
        int len = arr.length;
        int[][] dp = new int[len][len];

        // 初始化
        for (int i = 0;i < len;i++) dp[i][i] = arr[i];//只有一个值，就是他本身

        for (int i = len - 2;i > 0;i--)
            for (int j = i+1; j < len; j++)
                dp[i][j] = Math.max(arr[i] - dp[i+1][j],arr[i] - dp[i][j-1]);

        return dp[0][len-1] >= 0;
    }

}
